The Code Kata Challenge has past but today let’s review the code from our 3rd place winner who takes home the first copy of Are You Smart Enough to Work at Google?.
Challenge review:
- Implement a queue class using 2 stacks internally
- The queue class should implement an insert and retrieve method
- The 2 internal stacks should implement push and pop methods
Third place goes to Steve!
While Steve’s solution is clean it also gets extra points for efficiency.
Chris’ honorable mention post took the approach to copy everything in stack 1 (the add/insert stack) over to stack 2 except for the final element in stack 1, which was to be returned from the overall retrieve method, and then copy everything in stack 2 back over to stack 1, for every retrieval (in case another insert operation occurs in between retrievals).
However this isn’t quite necessary, as Steve’s solution and later solutions will show. For the efficiency of the solution, it is awarded third place.
Steve – Great work!
Invitations still available – so join us for Code Kata Night on July 10th from 3-5pm!
| import java.util.NoSuchElementException; | |
| import java.util.Stack; | |
| public class Queue<T> { | |
| private Stack<T> queueOrderedStack = new Stack<>(); | |
| private Stack<T> elementPlaceholder = new Stack<>(); | |
| public void add(T element) { | |
| elementPlaceholder.push(element); | |
| } | |
| public T remove() { | |
| if (queueOrderedStack.isEmpty()) { | |
| if (elementPlaceholder.isEmpty()) { | |
| throw new NoSuchElementException("Queue empty, must insert a value first before removing an item."); | |
| } | |
| orderStackForRetrieval(); | |
| } | |
| return queueOrderedStack.pop(); | |
| } | |
| private void orderStackForRetrieval() { | |
| if (!queueOrderedStack.isEmpty()) { | |
| throw new IllegalStateException("Cannot push new items onto ordered stack when items already exist."); | |
| } | |
| while (!elementPlaceholder.isEmpty()) { | |
| queueOrderedStack.push(elementPlaceholder.pop()); | |
| } | |
| } | |
| } |
| import static org.junit.Assert.assertEquals; | |
| import static org.junit.Assert.assertNull; | |
| import java.util.NoSuchElementException; | |
| import org.junit.Test; | |
| public class QueueTest { | |
| @Test | |
| public void simpleAddRemove() { | |
| Queue<Integer> queue = new Queue<>(); | |
| queue.add(25); | |
| queue.add(50); | |
| assertEquals(new Integer(25), queue.remove()); | |
| assertEquals(new Integer(50), queue.remove()); | |
| queue.add(75); | |
| assertEquals(new Integer(75), queue.remove()); | |
| } | |
| @Test | |
| public void addRemoveOutOfOrder() { | |
| Queue<Integer> queue = new Queue<>(); | |
| queue.add(25); | |
| queue.add(50); | |
| assertEquals(new Integer(25), queue.remove()); | |
| queue.add(75); | |
| assertEquals(new Integer(50), queue.remove()); | |
| queue.add(100); | |
| assertEquals(new Integer(75), queue.remove()); | |
| assertEquals(new Integer(100), queue.remove()); | |
| } | |
| @Test | |
| public void addRemoveNull() { | |
| Queue<Integer> queue = new Queue<>(); | |
| queue.add(25); | |
| queue.add(null); | |
| queue.add(50); | |
| assertEquals(new Integer(25), queue.remove()); | |
| assertNull("Null value should have been added to queue.", queue.remove()); | |
| assertEquals(new Integer(50), queue.remove()); | |
| } | |
| @Test(expected = NoSuchElementException.class) | |
| public void removeEmpty() { | |
| new Queue<>().remove(); | |
| } | |
| @Test(expected = NoSuchElementException.class) | |
| public void removeTooManyElements() { | |
| Queue<Integer> queue = new Queue<>(); | |
| queue.add(10); | |
| assertEquals(new Integer(10), queue.remove()); | |
| queue.remove(); | |
| } | |
| } |